package src.java.medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution380 {
    List<Integer> list;
    Map<Integer, Integer> map;

    public Solution380() {
        list = new ArrayList();
        map = new HashMap();
    }

    public static void main(String[] args) {
        Solution380 obj = new Solution380();
        System.out.println(obj.insert(1));
        System.out.println(obj.remove(2));
        System.out.println(obj.insert(2));
        System.out.println(obj.getRandom());
        System.out.println(obj.remove(1));
        System.out.println(obj.insert(2));
        System.out.println(obj.getRandom());
    }

    public boolean insert(int val) {
        if (this.map.containsKey(val)) return false;
        int index = list.size();
        this.map.put(val, index);
        this.list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!this.map.containsKey(val)) return false;
        Integer index = map.get(val);
        int size = list.size();
        Integer last = list.get(size - 1);
        list.set(index, last);
        this.map.put(last, index);
        this.list.remove(size - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int size = this.list.size();
        int index = (int) (Math.random() * size);
        return this.list.get(index);
    }
}
